1. 算法概述

• 目标：给定一个带权重的有向图或无向图，Floyd 算法能够找出其中任意两个顶点之间的最短路径长度。
• 核心思想：动态规划 (Dynamic Programming)。
• 适用性：
  • 可以处理带有负权重的边。
  • 不能处理包含负权重环路（Negative Cycle）的图。如果图中存在负权环，那么两点之间的最短路径可能不存在（因为可以在环路里无限地走下去，使得路径长度变为负无穷）。不过，Floyd 算法可以用来检测负权环的存在。
  • 适用于稠密图，因为其时间复杂度与边的数量无关。

2. 核心思想：动态规划的精髓

Floyd 算法的精髓在于一个非常巧妙的递推思想：“我到你那里，要不要从他那里中转一下？”

我们定义一个三维的状态：dp[k][i][j]

• dp[k][i][j] 的含义：从顶点 i 出发，只允许经过编号从 0 到 k 的顶点作为中间点，到达顶点 j 的最短路径长度。

现在，我们来建立状态转移方程。当我们计算 dp[k][i][j] 时，对于从 i 到 j 的最短路径，这个路径有两种可能：

1. 不经过新引入的中间点 k：

   • 这意味着，从 i 到 j 的最短路径，其所有中间点都在 {0, 1, ..., k-1} 集合中。
   • 这个路径的长度就是 dp[k-1][i][j]。

2. 经过新引入的中间点 k：

   • 这意味着，路径可以被分解为 i -> ... -> k -> ... -> j。
   • 为了让总路径最短，i -> k 的部分和 k -> j 的部分也必须是它们各自的最短路径。
   • 由于 k 已经是中间点了，所以从 i 到 k 和从 k 到 j 的路径中，所有中间点都只能在 {0, 1, ..., k-1} 集合中。
   • 所以，这条路径的长度是 dp[k-1][i][k] + dp[k-1][k][j]。

状态转移方程： 我们将以上两种情况取一个最小值，就得到了 dp[k][i][j] 的值。 dp[k][i][j] = min( dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j] )

空间优化： 我们发现，计算 dp[k] 这一层的数据时，只依赖于 dp[k-1] 层。这提示我们可以使用滚动数组的思想进行空间优化。实际上，我们可以把 k 这个维度直接去掉，只用一个二维数组 dist[i][j]。

dist[i][j] 的含义在迭代过程中是动态变化的：在第 k 轮迭代中，dist[i][j] 表示从 i 到 j 只允许经过 {0, ..., k-1} 作为中间点的最短路径。当我们用 k 进行更新时，它就变成了允许经过 {0, ..., k} 的最短路径。

优化后的状态转移方程（也是我们实际编码时使用的）： dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )

这个方程的含义是：从 i 到 j 的当前最短路径 dist[i][j]，与“从 i 先到 k，再从 k 到 j”这条新路径 dist[i][k] + dist[k][j] 相比，哪个更短？

3. 算法步骤

1. 初始化 dist 矩阵：

   • 创建一个 V x V 的矩阵 dist（V是顶点数量）。
   • dist[i][j] 初始化为从 i 到 j 的直接边的权重。
   • 如果 i 和 j 之间没有直接相连的边，则 dist[i][j] = ∞ (一个足够大的数)。
   • 对于对角线上的元素，dist[i][i] = 0 (自己到自己的距离为0)。

2. 三重循环迭代：

   • 这是算法的核心部分，完美地体现了动态规划的思想。
   • 最外层循环 k：从 0 到 V-1。k 代表当前允许作为“中转站”的顶点。这个 k 必须在最外层循环，因为我们要用一个固定的 k 来更新所有 (i, j) 对的路径。
   • 中间层循环 i：从 0 到 V-1。i 代表路径的起始点。
   • 最内层循环 j：从 0 到 V-1。j 代表路径的终点。
   • 在循环体内，执行更新操作：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。

3. 完成：

   • 当三重循环结束后，dist 矩阵中存储的就是任意两点之间的最短路径长度。

4. 实例推演

假设我们有如下的图（4个顶点）：

Step 1: 初始化 dist 矩阵 (k=-1，即无中转点) (用 INF 代表无穷大)

Step 2: 迭代

k = 0 (允许经过顶点0中转) 我们检查是否 dist[i][0] + dist[0][j] < dist[i][j]。

• i=1, j=3: dist[1][0] + dist[0][3] = 2 + 5 = 7。dist[1][3] 原本是4。min(4, 7) 还是4。
• … (检查所有 i, j 对，发现没有路径能通过0中转而变短) 矩阵不变。

k = 1 (允许经过顶点1中转)

• i=0, j=3: dist[0][1] + dist[1][3] = 3 + 4 = 7。dist[0][3] 原本是5。min(5, 7) 还是5。
• i=2, j=0: dist[2][1] + dist[1][0] = 1 + 2 = 3。dist[2][0] 原本是INF。min(INF, 3) 是3。更新 dist[2][0] = 3。
• i=2, j=3: dist[2][1] + dist[1][3] = 1 + 4 = 5。dist[2][3] 原本是INF。min(INF, 5) 是5。更新 dist[2][3] = 5。

更新后的矩阵：

k = 2 (允许经过顶点2中转)

• i=0, j=1: dist[0][2] + dist[2][1] (INF+1=INF)。不变。
• i=3, j=1: dist[3][2] + dist[2][1] = 2 + 1 = 3。dist[3][1] 原本是INF。更新 dist[3][1] = 3。
• i=3, j=0: dist[3][2] + dist[2][0] = 2 + 3 = 5。dist[3][0] 原本是INF。更新 dist[3][0] = 5。

…继续这个过程直到 k=3。

最终矩阵 (k=3 迭代完成后)

例如，dist[0][2] = 7，它代表了路径 0 -> 1 -> 3 -> 2，长度为 3 + 4 + 2，但这是错的。我们重新看 k=2 迭代后的矩阵： dist[0][1] = 3, dist[3][2]=2… 我们重新梳理一下 k=2 的更新。 i=0, j=1: dist[0][2] 是INF, 不更新。 i=1, j=2: dist[1][0] + dist[0][2], INF, 不更新。 … dist[0][2] 什么时候更新的？ 应该是 k=3 时, 通过 0->3->2 更新的。dist[0][3]+dist[3][2]=5+2=7。所以 dist[0][2] 变成7.

最终，这个矩阵就是所有点对之间的最短路径。

5. C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// 定义一个足够大的数作为无穷大
const int INF = 1e9;
 
void floyd_warshall(vector<vector<int>>& dist) {
    int n = dist.size();
    if (n == 0) return;
 
    // k 是中转点
    for (int k = 0; k < n; ++k) {
        // i 是起始点
        for (int i = 0; i < n; ++i) {
            // j 是终点
            for (int j = 0; j < n; ++j) {
                // 防止因 INF 相加导致整数溢出
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    // 更新 dist[i][j]
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}
 
void print_matrix(const vector<vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int val : row) {
            if (val == INF) {
                cout << "INF\t";
            } else {
                cout << val << "\t";
            }
        }
        cout << endl;
    }
}
 
int main() {
    int num_vertices = 4;
    // 初始化邻接矩阵
    vector<vector<int>> dist = {
        {0, 3, INF, 5},
        {2, 0, INF, 4},
        {INF, 1, 0, INF},
        {INF, INF, 2, 0}
    };
 
    cout << "Initial distance matrix:" << endl;
    print_matrix(dist);
 
    floyd_warshall(dist);
 
    cout << "\nAll-pairs shortest paths matrix:" << endl;
    print_matrix(dist);
 
    // 检查负权环
    for (int i = 0; i < num_vertices; ++i) {
        if (dist[i][i] < 0) {
            cout << "\nGraph contains a negative-weight cycle!" << endl;
            break;
        }
    }
 
    return 0;
}

6. 负权环检测

Floyd 算法完成后，如何判断图中是否存在负权环？ 非常简单：检查 dist 矩阵的对角线。

• 如果 dist[i][i] 的值小于 0，则说明从顶点 i 出发，经过一个环路再回到 i，路径长度是负数。这就证明了图中存在负权环。

这是因为，在算法开始时，dist[i][i] 都被初始化为 0。只有当存在一条从 i 出发回到 i 的负权路径时，dist[i][i] 的值才会被更新为负数。

7. 算法特性总结